CF138C Mushroom Gnomes - 2

偏模板的用线段树优化的简单概率期望题

题解：

首先转化题意，题目问所有蘑菇价值和的期望，由于期望的线性性，这等同于在问你每个蘑菇期望价值之和，已知价值，只要求出每个蘑菇不被覆盖的概率即可

思路很好想，对于每棵树，在它的左边做个区间乘，在它的右边做个区间乘，乘上的是1-倒下的概率，最后再单点查询每个蘑菇不被覆盖的概率

另外，因为注意到范围为1e9，所以还要离散化，对于每棵树的操作，只记录左边的两个端点和右边的两个端点

特别的，在代码中，由于询问都在修改之后，所以标记直接保留在线段上即可，不用上下传，只要查询的时候一直累乘即可

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5,M=1e4+5,NM=N*4+M,TR=NM<<2;
int n,m,pt[NM],pn;
double p[TR],ans;

struct tree{
    int x,h,l,r;
}a[N];

struct mushroom{
    int x,v;
}b[M];

void build(int x,int l,int r){
    p[x]=1; //初始概率都为1
    if(l==r) return ;
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}

void up(int x,int l,int r,int L,int R,double v){
    if(L<=l&&r<=R){
        p[x]*=v;
        return ;
    }
    int mid=l+r>>1;
    if(L<=mid) up(x<<1,l,mid,L,R,v);
    if(R>mid) up(x<<1|1,mid+1,r,L,R,v);
}

double que(int x,int l,int r,int pos){
    if(l==r) return p[x];
    int mid=l+r>>1;
    if(pos<=mid) return p[x]*que(x<<1,l,mid,pos); //把标记累乘
    return p[x]*que(x<<1|1,mid+1,r,pos);
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(a[i].x);read(a[i].h);read(a[i].l);read(a[i].r);
        pt[++pn]=a[i].x-a[i].h; //pt储存有用的端点信息
        pt[++pn]=a[i].x-1;
        pt[++pn]=a[i].x+1;
        pt[++pn]=a[i].x+a[i].h;
    }
    for(int i=1;i<=m;i++){
        read(b[i].x);read(b[i].v);
        pt[++pn]=b[i].x;
    }
    sort(pt+1,pt+1+pn);
    pn=unique(pt+1,pt+1+pn)-pt-1;
    build(1,1,pn);
    for(int i=1;i<=n;i++){
        up(1,1,pn,lower_bound(pt+1,pt+1+pn,a[i].x-a[i].h)-pt,lower_bound(pt+1,pt+1+pn,a[i].x-1)-pt,1.0-0.01*a[i].l); //乘左边
        up(1,1,pn,lower_bound(pt+1,pt+1+pn,a[i].x+1)-pt,lower_bound(pt+1,pt+1+pn,a[i].x+a[i].h)-pt,1.0-0.01*a[i].r); //乘右边
    }
    for(int i=1;i<=m;i++)
        ans+=que(1,1,pn,lower_bound(pt+1,pt+1+pn,b[i].x)-pt)*b[i].v; //查询概率并乘上价值
    printf("%.10lf",ans);
}